package com.kingwood.algorithm.test;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @Author 22025812
 * @Description: TODO
 * @Date: 2024/2/27 13:34
 * @Modified By：
 * @Version 1.0
 */
public class ErFen {
    /**
     * 机器人搬砖
     */
    public static int robotNeedEnergy(int[] bricks) {
        if (bricks.length == 0 || bricks.length > 8) {
            return -1;
        }

        int max = Arrays.stream(bricks).max().orElse(0);
        if (bricks.length == 8) {
            return max;
        }

        int min = 1;
        int ans = max;

        while (min <= max) {
            int mid = (min + max) >> 1;

            if (check(mid, 8, bricks)) {
                ans = mid;
                max = mid - 1;
            } else {
                min = mid + 1;
            }
        }

        return ans;
    }

    public static boolean check(int energy, int limit, int[] bricks) {
        int cost = 0;
        for (int brick : bricks) {
            cost += brick / energy + (brick % energy == 0 ? 0 : 1);
            if (cost > limit) {
                return false;
            }
        }

        return true;
    }

    /**
     * 小明找位置
     * https://blog.csdn.net/qfc_128220/article/details/134640116
     * 小朋友出操，按学号从小到大排成一列；
     * 小明来迟了，请你给小明出个主意，让他尽快找到他应该排的位置。
     * 算法复杂度要求不高于nLog(n)；学号为整数类型，队列规模 ≤ 10000；
     * @param arr
     * @param num
     * @return
     */
    public static int xiaoMingFindPos(int[] arr, int num) {
        int pos = 0;
//        Arrays.sort(arr);
        int min = 0;
        int max = arr.length-1;

        while (min <= max) {
            pos = (min + max) >> 1;
            if (arr[pos] > num) {
                max = pos-1;
            } else {
                min = pos+1;
            }
        }

        return min+1;
    }

    public static int findLeft(int[] arr, int num) {
        int left = 0;
        int right = arr.length-1;
        int m = 0;
        int ans = -1;

        while (left <= right) {
            m = (left + right) >> 1;
            if (arr[m] >= num) {
                ans = m;
                right = m-1;
            } else {
                left = m+1;
            }
        }

        return ans;
    }

    /**
     * https://leetcode.cn/problems/find-peak-element/
     * 这个题是返回任何一个峰值 所在位置即可。
     * @param arr
     * @return
     */
    public static int findPeakElement(int[] arr) {
        int n = arr.length;
        if (n == 1) {
            return 0;
        }

        if (arr[0] > arr[1]) {
            return 0;
        }

        if (arr[n-1] > arr[n-2]) {
            return n - 1;
        }

        int l = 1, r = n - 2, m = 0, ans = -1;
        while (l <= r) {
            m = (l + r) / 2;
            if (arr[m-1] > arr[m]) {
                r = m - 1;
            } else if (arr[m] < arr[m+1]) {
                l = m + 1;
            } else {
                ans = m;
                break;
            }
        }

        return ans;
    }

    /**
     * 猴子吃桃，星星吃香蕉，机器人搬砖
     * https://blog.csdn.net/qfc_128220/article/details/134383579
     * @param arr 每个桃树上桃子的数量
     * @param h 守卫离开的小时数
     * @return
     */
    public static int getMinSpeed(int[] arr, int h) {
        int ans = 0;
        int len = arr.length;
        if (h > len) {
            return -1;
        }

        int maxCount = 0;
        for (int i=0; i<len; i++) {
            if (arr[i] > maxCount) {
                maxCount = arr[i];
            }
        }

        if (h == len) {
            return maxCount;
        }

        int min = 1;
        // 在min 和max之间寻找最小的值
        while (min <= maxCount) {
            int mid = (min + maxCount) >> 1;
            // 如果以mid速度，可以在h小时内吃完cnts所有桃，那么mid就是一个可能解
            if (checkCurSpeed(mid, h, arr)) {
                ans = mid;
                maxCount = mid - 1;
            } else {
                min = mid + 1;
            }
        }

        return ans;
    }

    public static boolean checkCurSpeed(int speed, int h, int[] arr) {
        int cost = 0;
        for (int n : arr) {
            cost += n / speed + (n % speed > 0 ? 1 : 0);
            if (cost > h) {
                return false;
            }
        }
        return true;
    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
//        int[] bricks = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
//        System.out.println(robotNeedEnergy(bricks));

        int[] arr = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
//        int num = scanner.nextInt();
//        System.out.println(xiaoMingFindPos(arr, num));
        System.out.println(findPeakElement(arr));
    }
}
